Integrated Multimedia Services (IMS) are being deployed in 3G cdma2000 type public wireless networks connected to Internet Protocol (IP) networks. However, the wireless and IP networks utilize certain incongruent quality of service (QoS) scheduling strategies, which results in sub optimal prioritized packet scheduling decisions. For example, on the downlink scheduling of packets in cdma2000 1xEV-DO cellular networks, there is a clear misalignment due to the two distinct QoS domains of the wireless and wireline IP networks. The public wireless cellular networks typically use QoS algorithms based on Proportional Fairness (PF). PF is concerned with deciding which packet to transmit in a particular time slot on a single shared broadband channel, based on fair allocation of bandwidth and maximizing system throughput. In contrast, the IP networks forming the Internet and various wireline Intranets typically use QoS algorithms based on Generalized Processor Sharing (GPS), in particular Weighted Fair Queuing (WFQ), which decides which packet to transmit in a particular time slot out to an egress port based on fair allocation of bandwidth and minimizing average flow delay for well behaved or policed traffic. Blindly integrating these two networks, with their associated scheduling mechanisms, may result in sub optimal resource allocations leading to excessive and unnecessary delays for certain users.
FIG. 1 depicts a typical implementation of a 3GPP2 1xEV-DO network. The drawing shows network elements in high-level functional block diagram form, and it shows certain aspects of the processing involved in communications through the illustrated elements. The mobile device, sometimes referred to as a mobile User Agent (UA), communicates through a Base Transmitter Station (BTS), selected from among those that the mobile device can detect (approximately within range) over the air, ending up with the BTS with the best Channel to Interference ratio. The High Rate Packet Data Interface (HPRD) on this wireless network segment or domain is the most expensive and narrow capacity network connection amongst all segments (represented thematically by the pipes of various sizes/bandwidths) that will carry the UA's communication. The packet scheduler on this segment may reside in a DOM module (Data Optimized Module) as one example of an implementation. The DOM, typically in the form of a card that fits in a Base Transmitter Station (BTS), communicates with the UA mobile device over the air link using a specific frequency spectrum. The scheduler in the DOM optimizes system throughput based on a proportional fairness algorithm (PF), represented by the functional block in the diagram.
The next segment connects the BTS to the Radio Network Controller (RNC), located in the Mobile Switching Center (MSC). This wireline segment traditionally utilized, TDMA based T1 circuits, but the segment is now evolving to utilize Metro Ethernet connections provided by Regional Service providers. These links are typically 10/100 Mbs capacity. The metro Ethernet connection on the MSC side is typically on the order of a gigabit link capacity. The wireline packet scheduler in the RNC, on the forward link typically uses a variant of Weighted Fair Queuing (WFQ), represented by the functional block in the diagram. Least latency queuing (LLQ) is often implemented since it combines a strict priority queue with WFQ to support real time traffic. The rest of the wireline network segments all use some form of WFQ packet scheduler, as shown by the WFQ scheduler blocks in the diagram. WFQ is designed to minimize average latency for all flows. Although shown separately for illustration purposes, the PF and WFQ scheduler functions typically are functional aspects of the relevant routing elements, such as those in or associated with the DOM and RNC.
The wireline network segment between the IP backhaul and HPRD, on the forward link (arrow representing traffic communication from the IP core network going to mobile station UA), has a clear misalignment of optimizations. This segment extends out to and includes a portion of the Data Optimized Module (DOM), at the BTS. The DOM implements a special algorithm to transmit/(receive) data to/(from) the mobile devices via the wireless network domain, including the air link(s) to and from the UA mobile devices. DOM has been developed to implement 1xEV-DO type wireless packet communication service—a type of CDMA protocol for high speed packet data transmission for mobile networks. The wireless PF type packet scheduler implemented in the DOM module tries to maximize system throughput, whereas the WFQ type wireline packet schedulers used for forwarding of packets to the DOM minimize average latency.
The core portion of the network may be implemented in a variety of different ways, which will provide adequate transport capability for the IP packet traffic. For purposes of showing a complete example, the core is shown using is Multi Protocol Label Switching (MPLS) fast efficient forwarding of packets over asynchronous transfer mode (ATM) cell type transport. The lower portion of the drawing shows the protocol stacks for an exemplary implementation of the illustrated network. Those skilled in the art will recognize that various networks may utilize these or other combinations of communications protocols.
FIGS. 2A to 2C depict in more detail, exemplary problems that may arise when connecting a wireline network to a wireless network. FIG. 2A shows the general case where two equal priority subscribers experience different congestion and different amounts of traffic on the forward links. Packets bound for each subscriber are placed in queue at a router in the wireline part of the network, which implements WFQ scheduling. The router selects packets from the various queues and passes the packets, as scheduled, to the wireless portion of the network. In the wireless portion of the network, packets are placed in queue by an element such as the DOM, which utilizes the PF scheduling algorithm. The BTS transmits packets from the queues, as scheduled by application of the PF algorithm, over the air link to the mobile station client devices of the respective subscribers.
In the example, the subscriber I client device has a remote connection to a server over a very uncongested link, and hence is receiving a large burst of traffic (represented by the wide dotted line pipes in FIG. 2A). The subscriber 2 client device, on the other hand, has a remote server connection over a very congested link (represented by the narrow dotted line pipes in FIG. 2A) and is receiving a very small amount of packet traffic. Two problems arise in this case.
FIGS. 2B and 2C show the relevant queues at the respective routers, which will handle the packets for the two subscribers as they pass out of the wireline domain and through the wireless network to the client devices.
As shown in FIG. 2B, since they are of the same priority, if the wireline network device is using class based queuing, not per flow queues implemented in the WFQ scheduling, the WFQ scheduler just places any new data for subscriber 2 in the one outbound queue behind any data already scheduled for transmission to subscriber 1. Since there is much more data for subscriber 1, there will often be a substantial number of packets ahead of any packets for subscriber 2 at the time of WFQ scheduling.
Since the wireline network is usually over-provisioned, it is easy to see that in the wireless domain element, the subscriber 1 will have many more packets in its queue than subscriber 2 (subscriber 1 has a full queue, while that for subscriber 2 is empty in the example). The subscriber 1 transmissions are able to fill up the queue of subscriber 1 at a relatively higher rate than subscriber 2 because of the routing and scheduling through the wireline part of the network.
The PF algorithm used by the scheduler for the wireless link will basically give a higher preference to a particular subscriber based on the amount of packets in the queue for that subscriber and/or the amount of bandwidth the air link can handle between a particular mobile subscriber device and the Access Network. In the example, the PF scheduler continually gives higher priority to subscriber 1, because that subscriber has more packets in its queue. Hence, it is very easy for subscriber 1 to hog all the bandwidth, and virtually starve out subscriber 2. The condition can be particularly problematic, if the radio conditions are equal, and subscriber 1 is of lower priority. The PF scheduler will unfairly give a higher number of time slots to subscriber 1, even though the two subscribers are of the same priority.
The second problem is shown in FIG. 2C. Now, there are per flow queues implemented in the wireline element performing the WFQ scheduling. In the example, assume subscriber 1 traffic has the higher priority. WFQ schedules traffic at least in significant part based on priority, therefore whenever the element performing the WFQ scheduling has packets to send for both subscribers, it will forward those for subscriber 1 first, based on the higher priority of that subscriber's traffic. Even though subscriber 1 is given higher priority in transmission, packets for subscriber 1 will keep the queue for that subscriber relatively full, because of the number of packets supplied through its broadband session from the server (see also FIG. 2A).
Due to differences in network congestion, the lower priority traffic is delayed significantly on the wireline network. This wireline network delay may reach a point at which the lower priority traffic will be dropped if it is not sent immediately to the subscriber 2 client device. However, because the WFQ scheduling gives priority to subscriber 1 and subscriber 1 has a relatively full queue, the wireline router still sends packets for subscriber 1 before transmitting packets for subscriber 2. This tends to keep packets for subscriber 1 in the queue in wireless domain, so that the PF scheduler continually gives higher priority to subscriber 1. In the example, the queue that contains subscriber 1 packets, at the wireless routing element using PF scheduling, is relatively full. At the same time, the queue for subscriber 2 at that element contains few, if any, data packets. As a result, subscriber 1 traffic is given priority and is transmitted to the client device significantly below the time delay budget. Here we clearly see that the WFQ scheduling is concerned with minimizing local average delay of the flows in each queue and that the PF algorithm is concerned with maximizing system throughput on the air link. What is missing is something that also considers the global goal of meeting time budgets of all flows but ensuring higher priority traffic is not delayed beyond a noticeable amount to subscribers.
Another obvious problem occurs when the PF function in the wireless network schedules packets based on channel condition. If the PF algorithm does not consider the notion of priority of the queue, then it can be clearly seen that low priority users, with consistently good channel conditions will be allocated more network resources and be given preferential treatment over higher priority subscribers.
As shown by the discussion above, a problem exists with End to End QoS Packet scheduling parameters, when deploying time sensitive network traffic onto combinations of 3G cdma2000 1xEV-DO networks and IP networks. The packet scheduling algorithms were not designed for hybrid deployments from wireless to wireline packet sessions, resulting in sub optimal resource allocations. A need exists to improve scheduling algorithms for time sensitive services, such as integrated multimedia services, through combinations of wireless and wireline packet (e.g. IP) networks that avoid resource allocation problems and/or improve performance.